package com.leetcode.algorithm.y19.m01;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * (done)112. 路径总和
 * (done)501. 二叉搜索树中的众数
 * (done)538. 把二叉搜索树转换为累加树
 * (done)543. 二叉树的直径
 * (done)563. 二叉树的坡度
 * (done)572. 另一个树的子树
 * @author: jie.deng
 * @time: 2019年1月24日 上午9:06:59
 */
public class MySolution0124 {
	
	/**
	 * 112. 路径总和
	 * 
   * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
   * 
   * 说明: 叶子节点是指没有子节点的节点。
   * 
   * 示例: 
   * 给定如下二叉树，以及目标和 sum = 22，
   * 
   *               5
   *              / \
   *             4   8
   *            /   / \
   *           11  13  4
   *          /  \      \
   *         7    2      1
   * 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
	 * @param root
	 * @param sum
	 * @return
	 */
	public boolean hasPathSum(TreeNode root, int sum) {
		if (root == null) {
			return false;
		}
		if (root.left == null && root.right == null) {
			return sum == root.val;
		} else if (root.left == null) {
			return hasPathSum(root.right, sum - root.val);
		} else if (root.right == null) {
			return hasPathSum(root.left, sum - root.val);
		} else {
			return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
		}
    }
    
	/**
	 * 501. 二叉搜索树中的众数
	 * 
   * 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
   * 
   * 假定 BST 有如下定义：
   * 
   * 结点左子树中所含结点的值小于等于当前结点的值
   * 结点右子树中所含结点的值大于等于当前结点的值
   * 左子树和右子树都是二叉搜索树
   * 例如：
   * 给定 BST [1,null,2,2],
   * 
   *    1
   *     \
   *      2
   *     /
   *    2
   * 返回[2].
   * 
   * 提示：如果众数超过1个，不需考虑输出顺序
   * 
   * 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
	 * @param root
	 * @return
	 */
	public int[] findMode(TreeNode root) {
		List<Integer> list = inorderTreeNode(root);
		if (list == null || list.size() == 0) {
			return new int[] {};
		}
		List<Integer> ret = new ArrayList<Integer>();
		int size = list.size();
		int maxCnt = 1;
		for (int i = 0; i < size;) {
			int curVal = list.get(i);
			int j = i + 1;
			for (; j < size; j++) {
				if (list.get(j) != curVal) {
					break;
				}
			}
			if (j - i > maxCnt) {
				maxCnt = j - i;
				ret.clear();
				ret.add(curVal);
			} else if (j - i == maxCnt) {
				ret.add(curVal);
			}
			i = j;
		}

		int[] retArr = new int[ret.size()];
		for (int j = 0; j < ret.size(); j++) {
			retArr[j] = ret.get(j);
		}
		return retArr;
	}

	private List<Integer> inorderTreeNode(TreeNode node) {
		List<Integer> list = new ArrayList<Integer>();
		if (node == null) {
			return list;
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode cur = node;
		while (cur != null || !stack.isEmpty()) {
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			if (!stack.isEmpty()) {
				cur = stack.pop();
				list.add(cur.val);
				cur = cur.right;
			}
		}
		return list;
	}

	/**
     * 538. 把二叉搜索树转换为累加树
     * 
     * 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
     * 
     * 例如：
     * 
     * 输入: 二叉搜索树:
     *               5
     *             /   \
     *            2     13
     * 
     * 输出: 转换为累加树:
     *              18
     *             /   \
     *           20     13
     * @param root
     * @return
     */
	public TreeNode convertBST(TreeNode root) {
		// 右中左的遍历方式 和 累加处理
		convertBST(root, 0);
		return root;
	}

	private int convertBST(TreeNode node, int sum) {
		if (node == null) {
			return sum;
		}
		sum = convertBST(node.right, sum);
		sum += node.val;
		node.val = sum;
		sum = convertBST(node.left, sum);
		return sum;
	}

	/**
     * 543. 二叉树的直径
     * 
     * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
     * 
     * 示例 :
     * 给定二叉树
     * 
     *           1
     *          / \
     *         2   3
     *        / \     
     *       4   5    
     * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
     * 
     * 注意：两结点之间的路径长度是以它们之间边的数目表示。
     * @param root
     * @return
     */
	public int diameterOfBinaryTree(TreeNode root) {
		if (root == null || (root.left == null && root.right == null)) {
			return 0;
		}
		int left = diameterOfBinaryTree(root.left);
		int right = diameterOfBinaryTree(root.right);
		return Math.max(getMaxDepth(root.left, 0) + getMaxDepth(root.right, 0), Math.max(left, right));
	}

	private int getMaxDepth(TreeNode node, int depth) {
		if (node == null) {
			return depth;
		}
		depth += 1;
		return Math.max(getMaxDepth(node.left, depth), getMaxDepth(node.right, depth));
	}

	/**
     * 563. 二叉树的坡度
     * 
     * 给定一个二叉树，计算整个树的坡度。
     * 
     * 一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
     * 
     * 整个树的坡度就是其所有节点的坡度之和。
     * 
     * 示例:
     * 
     * 输入: 
     *          1
     *        /   \
     *       2     3
     * 输出: 1
     * 解释: 
     * 结点的坡度 2 : 0
     * 结点的坡度 3 : 0
     * 结点的坡度 1 : |2-3| = 1
     * 树的坡度 : 0 + 0 + 1 = 1
     * 注意:
     * 
     * 任何子树的结点的和不会超过32位整数的范围。
     * 坡度的值不会超过32位整数的范围。
     * @param root
     * @return
     */
	public int findTilt(TreeNode root) {
		return findTilt(root, new Stack<Integer>(), 0);
	}

	private int findTilt(TreeNode node, Stack<Integer> sumStack, int tiltSum) {
		if (node == null) {
			sumStack.push(0);
			return tiltSum;
		}
		tiltSum = findTilt(node.left, sumStack, tiltSum);
		tiltSum = findTilt(node.right, sumStack, tiltSum);
		Integer right = sumStack.pop();
		Integer left = sumStack.pop();
		sumStack.push(right + left + node.val);
		tiltSum += Math.abs(right - left);
		return tiltSum;
	}

	/**
     * 572. 另一个树的子树
     * 
     * 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
     * 
     * 示例 1:
     * 给定的树 s:
     * 
     *      3
     *     / \
     *    4   5
     *   / \
     *  1   2
     * 给定的树 t：
     * 
     *    4 
     *   / \
     *  1   2
     * 返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
     * 
     * 示例 2:
     * 给定的树 s：
     * 
     *      3
     *     / \
     *    4   5
     *   / \
     *  1   2
     *     /
     *    0
     * 给定的树 t：
     * 
     *    4
     *   / \
     *  1   2
     * 返回 false。
     * @param s
     * @param t
     * @return
     */
	public boolean isSubtree(TreeNode s, TreeNode t) {
		if (s == null || t == null) {
			return s == t;
		}
		if (s.val == t.val && isSame(s.left, t.left) && isSame(s.right, t.right)) {
			return true;
		}
		return isSubtree(s.left, t) || isSubtree(s.right, t);
	}

	private boolean isSame(TreeNode s, TreeNode t) {
		if (s == null || t == null) {
			return s == t;
		}
		return s.val == t.val && isSame(s.left, t.left) && isSame(s.right, t.right);
	}
    
}
